package argo.hot100.recall;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LetterCombinations {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();

        if (digits == null || digits.length() == 0) {
            return res;
        }

        Map<Character, char[]> cdMap = new HashMap<>();
        cdMap.put('2', new char[]{'a', 'b', 'c'});
        cdMap.put('3', new char[]{'d', 'e', 'f'});
        cdMap.put('4', new char[]{'g', 'h', 'i'});
        cdMap.put('5', new char[]{'j', 'k', 'l'});
        cdMap.put('6', new char[]{'m', 'n', 'o'});
        cdMap.put('7', new char[]{'p', 'q', 'r', 's'});
        cdMap.put('8', new char[]{'t', 'u', 'v'});
        cdMap.put('9', new char[]{'w', 'x', 'y', 'z'});


        backtrace(digits, cdMap, res, new StringBuffer(), 0);

        return res;
    }

    public void backtrace(String digits, Map<Character, char[]> cdMap, List<String> res, StringBuffer subres, int index) {

        if (index == digits.length()) {
            res.add(subres.toString());
            return;
        }
        char[] chars = cdMap.get(digits.charAt(index));
        for (int i = 0; i < chars.length; i++) {
            subres.append(chars[i]);
            backtrace(digits, cdMap, res, subres, index + 1);
            subres.deleteCharAt(index);
        }

    }

}
